// Created by WXX on 2021/11/19 10:12
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/**
 * 执行用时：708 ms, 在所有 C++ 提交中击败了40.00%的用户
 * 内存消耗：274 MB, 在所有 C++ 提交中击败了12.00%的用户
 */
class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

        // row[i]第i行有灯的列，其余类似
        unordered_map<int, unordered_set<int>> row, col, dg, udg;
        for (auto &p : lamps) {
            int x = p[0], y = p[1];
            row[x].insert(y);
            col[y].insert(x);
            dg[y - x].insert(x);
            udg[x + y].insert(x);
        }

        vector<int> res;
        for (auto &q : queries) {
            int x = q[0], y = q[1];
            if (row[x].size() || col[y].size() || dg[y - x].size() || udg[x + y].size()) {
                res.push_back(1);
                for (int i = x - 1; i <= x + 1; i++)
                    for (int j = y - 1; j <= y + 1; j++) {
                        row[i].erase(j);
                        col[j].erase(i);
                        dg[j - i].erase(i);
                        udg[i + j].erase(i);
                    }
            } else {
                res.push_back(0);
            }
        }
        return res;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> lamps = {
            {0, 0},
            {4, 4}
    };
    vector<vector<int>> queries = {
            {1, 1},
            {1, 0},
    };
    OutputBasicArray1D(Solution().gridIllumination(5, lamps, queries));  // [1, 0]

    return 0;
}
